1. Field of the Invention
The present invention relates to a packet classification method, and more particularly to a packet classification method through hierarchical rulebase partitioning, which can reduce a search time required for packet classification by partitioning a rulebase into independent sub-rulebases through a plurality of hashing stages and classifying input packets only in a related sub-rulebase.
2. Description of Related Art
Packet classification is one of the most fundamental building blocks in many networking functions such as Diff-Serv traffic conditioning, firewall, VPN, traffic accounting and billing, load-balancing, and policy-based routing. These functions need to track flows and give the same treatment to the packets in a flow. A rulebase stores classification rules, which define the flows and their corresponding treatments. Since a flow is defined by the header values of a packet, a classfier's duty is to examine the header and identify the corresponding flow.
Internet traffic is not only fast growing, but it is also diversifying both in applications and in protocols. New applications and protocols such as Internet telephony, security protocols, and peer-to-peer applications are being rapidly deployed in addition to the traditional Internet applications such as Web, ftp, and email. As a result, the rulebase size is rapidly increasing. In a recent study [T. Woo, “A Modular Approach to Packet Classification: Algorithms and Results”, In Proceedings of the IEEE INFOCOM '00. March 2000.], Woo argues that a rulebase with over a million entries is possible in future packet classification applications. From the classifier's viewpoint, this implies that for each packet the classifier must be able to find the matching rule with the highest priority amongst all the rules in the rulebase at the wire speed. Thus, there has been a renewal of interest in the scalability issue in the terms of the size of a rulebase. [(1) P. Gupta and N. McKeown, “Packet Classification on Multiple Fields”, In Proceedings of the ACM SIGCOM '99, Vol. 29, issue 4, August 1999. (2) F. Baboescu and G. Varghese, “Scalable Packet Classification”, In Proceedings of the ACM SIGCOM '01, Vol. 31, August 2001. (3) Flow Analysis of Passive Measurement Data, http://pma.nlanr.net/PMA/Datacube.html. (4) T. V. Lakshman and D. Stiladis, “High-speed Policy-based Packet Forwarding using Efficient Multi-dimensional Range Matching”, In Proceedings of the ACM SIGCOMM '98 Vol. 28, pp. 191-202, 1998. (5) V. Srinivasan, S. Suri, G. Varghese, and M. Valdvogel, “Fast and Scalable Layer Four Switching”, In Proceedings of the ACM SIGCOMM '98, Vol. 28, pp. 203-214, 1998. (6) V. Srinivasan, G. Varghese, and S. Suri, “Packet Classification Using Tuple Space Search”, In Proceedings of the ACM SIGCOMM '99, Vol. 29, pp. 135-146, August 1999. (7) M. M. Buddhikot, S. Suri, and M. Waldvogel, “Space Decomposition Techniques for Fast Layer-4 Switching”, In Proceedings of the IFIP Sixth International Workshop on Protocols for High Speed Networks. Vol. 66, No. 6, pp. 277-283, August 1999. (8) A. Feldmann and S. Muthukrishnan, “Tradeoffs for packet Classification”, In Gigabit Networking Workshop of the Proceedings of the IEEE INFOCOM '00. March 2000. (9) P. Gupta and N. Mckeown, “Packet Classification using Hierarchial Intelligent Cuttings”, In Proceedings of the Hot Interconnects VII, 1999.]
Most of existing works, however, mainly focus on relatively small classifiers, for example, with less than 20 K rules. To address this issue, we propose a new scalable packet classification algorithm that can scale well up to this size.
Also, the conventional packet classification has problem as follows. Given a rulebase,
      R    =                  ∑                  i          =          1                n            ⁢              r        i              ,which is a set of rules, a packet classifier needs to identify the rule that incoming packet matches to by looking up one or more fields of the packet header. Each rule is specified by the range of values in one or more fields of a packet header. Specifically, in d-dimensional packet classification, each rule ri is defined over d fields. Formally, ri is defined by a tuple (Ci, Ai) where Ci is called a classification space and, Ai is the associated action of rule ri. The classification space is defined by the crossproduct,
            C      i        =                                        F            1                    ⊗                      F            2                    ⊗                                          ⁢          …                ⁢                                  ⁢                  F          d                    =                        ∏                      k            =            1                    d                ⁢                  F          k          i                      ,is a range of values the field k must take. A rule ri match a packet p={b1, b2, . . . , bd} if for
      ∀    k    ,            b      k        ∈          F      k      i      where bk is a singleton. Multiple rules can match a packet. Thus, a classifier must identify the highest priority rule among all the matching rules. Intuitively, this requires the classifier to lookup the header fields of an incoming packet and to compare them against the rules in the rulebase one by one in order of decreasing priority. When n, for example the number of rules, is large of arrival rate λ of incoming packet is high, this is a time-consuming serial process, which will limit the speed of the classifier. Thus, the essence of the problem is to find a fast yet scalable classification function both in time and in space.